package algocasts;

public class P26_longestPalindrome {
    // Time:O(n^2)  Space: O(n^2) 动态规划
    public String longestPalindrome_DP(String s) {
        if (s == null || s.length() == 0) return "";
        int n = s.length(), start = 0, maxLen = 0;
        // 从 i 开始到 j 的字串是否为回文串
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {      // 从最右边开始
            for (int j = i; j < n; j++) {       // 往右移动
                // i j 指向同一个字符
                if (i == j) dp[i][j] = true;
                    // i j 相邻
                else if (i + 1 == j) dp[i][j] = s.charAt(i) == s.charAt(j);
                    // i j 不相邻且不是同一个，两字符相等并且上一个字串是回文串才true
                else dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                // 更新最长字串的长度和起点
                if (dp[i][j] && (j - i + 1) > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }


    // Time: O(n^2)  Space: O(1) 中心点往两边扩展
    public String longestPalindrome_Expand(String s) {
        if (s == null || s.length() == 0) return "";
        int start = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i); // 同一起点扩展
            int len2 = expand(s, i, i + 1); // 相邻起点扩展
            int len = Math.max(len1, len2); // 取长的
            if (len > maxLen) { // 更新最长字串起点和长度
                start = i - (len - 1) / 2;
                maxLen = len;
            }
        }
        return s.substring(start, start + maxLen);
    }

    int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}
